/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void _Convert(TreeNode* root, TreeNode*& prev)
	{
		if (root == nullptr)
			return;
		_Convert(root->left, prev);
		root->left = prev;
		if (prev)
			prev->right = root;
		prev = root;
		_Convert(root->right, prev);
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {
		TreeNode* prev = nullptr;
		_Convert(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
		while (head && head->left)
			head = head->left;
		return head;
	}
};